//字符串的排列: https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?
class Solution {
  public:
    void swap(string& str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
    bool IsExist(vector<string>& result, string& str) {
        auto it = result.begin();
        for (; it != result.end(); ++it) {
            if (*it == str) {
                return true;
            }
        }
        return false;
    }
    void PermutationHelper(string& str, int start, vector<string>& result) {
        if (start == str.length() - 1) {
            if (!IsExist(result, str)) {
                result.push_back(str);
            }
            return;
        }
        for (int i = start; i < (int)str.size(); i++) {
            //start 和 i 的关系是：表示以谁开始
            swap(str, start, i);
            //当确定以哪个字符作为开始，就要在决定另一部分的排列组合种类
            //这里一定要深刻理解，i仅仅是决定以谁作为排列的开始，但是求sub字符串每次开始，都要从start+1开始
            PermutationHelper(str, start + 1, result);
            swap(str, start, i);
        }
    }
    vector<string> Permutation(string str) {
        vector<string> result;
        if (str.length() > 0) {
            PermutationHelper(str, 0, result);
            sort(result.begin(), result.end());
        }
        return result;
    }
};